import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 涛
 * Date: 2023-10-22
 * Time: 14:38
 */

/**
 * 前K个高频单词
 * https://leetcode.cn/problems/top-k-frequent-words/
 */
public class Sort {
    public List<String> topKFrequent(String[] words, int k) {
        //统计worlds中的单词个数
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if(map.get(word) == null) {
                map.put(word, 1);
            } else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }
        //创建一个小根堆，把map中的entry放进小根堆中
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //单词的频率相同，要转变为大根堆-》按照单词序
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                //频率比小根堆堆顶大的才入小根堆，不然就是不入
                Map.Entry<String, Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    //小根堆堆顶的频率比此时遍历的entry元素频率小,堆顶要出，entry要入
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        //频率相同就要判断字典序了
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            //小根堆堆顶的字母序比此时遍历的entry元素字母序小,堆顶要出，entry要入
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        //定义一个链表，把小根堆的元素依次放到这个链表中
        List<String> list = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            list.add(top.getKey());
        }
        //逆置小根堆
        Collections.reverse(list);
        //返回这个链表
        return list;
    }
}
